/*
 * @Author: zsk
 * @Date: 2021-12-11 11:40:38
 * @LastEditTime: 2021-12-12 15:22:24
 * @LastEditors: zsk
 * @Description: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 * @FilePath: /data-and-structure-lv/02/insertion/insertion-sort2.c
 */
#include <stdio.h>

typedef int ElementType;

int binary_search(ElementType *a, ElementType key, int p, int r)
{
    if (p > r)
    {
        return -1;
    }
    else if (p == r)
    {
        return key > a[p] ? p + 1 : p;
    }

    int mid = (p + r) / 2;
    if (key < a[mid])
    {
        binary_search(a, key, p, mid - 1);
    }
    else if (key > a[mid])
    {
        binary_search(a, key, mid + 1, r);
    }
    else if (key == a[mid])
    {
        return mid > 1 ? mid - 1 : 0;
    }
}

void insertion_sort(ElementType *a, int length)
{
    for (int j = 1; j < length; j++)
    {
        /* code */
        ElementType key = a[j];
        int i = j - 1;
        int index = binary_search(a, key, 0, i);
        while (i >= index)
        {
            /* code */
            a[i + 1] = a[i];
            i = i - 1;
        }
        a[i + 1] = key;
    }
}

void main()
{
    ElementType b[] = {1, 2, 3, 4, 5, 6};
    int length = 6;
    int index=binary_search(b, 2, 0, length-1);
    printf("index: %d\n",index);
    
    ElementType a[] = {5, 2, 4, 6, 1, 3};

    insertion_sort(a, length);
    for (int i = 0; i < length; i++)
    {
        /* code */
        printf("%d ", a[i]);
    }
    printf("\n");
}